package F.树;

import java.util.Stack;

public class _112_路径总和 {

    /**
     * 自解：只能前序遍历 利用栈
     * 如果相加小于sun push进栈 否则弹出一个继续遍历--复杂啦
     * 没出来
     *
     *
     * @param root
     * @param sum
     * @return
     */
    Stack<Integer> stack = new Stack<>();
    int result =0;
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root==null){
            return false;
        }

        if (result+ root.val < sum){
            stack.push(root.val);
            result += root.val;
        }else if (result+ root.val == sum){
            return true;
        }else {
            return false;
        }

        if (!hasPathSum(root.left,sum)){
            hasPathSum(root.right,sum);
        }else {
            return true;
        }

        return false;

    }

    /** 题解：：递归
     * 函数功能：询问是否存在从当前节点到叶子节点的路径 路径和为sum
     * 假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：
     * 是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。
     *
     * 若当前节点就是叶子节点，那么我们直接判断 sum 是否等于 val 即可
     *
     */

    public boolean hasPathSum1(TreeNode root, int sum) {

        if (root == null){
            return false;
        }

        if (root.left == null && root.right == null){
            return  root.val == sum;
        }

        return hasPathSum(root.right,sum- root.val) ||hasPathSum(root.left,sum- root.val);

    }

}
